public class textthree {//找出出现次数超过数组长度一半的数字
    public static int sort3(int[] arr,int a,int b){
        int[] arr1=seachersort(arr,a,b);//作为等于的区间
        int q=arr1[1]-arr1[0]+1;
        if(q>(arr.length>>1)){
            return arr[arr1[1]];
        }else if(a>=b) {
            return 0;
        }else {
           return sort3(arr,arr[1]+1,b)+sort3(arr,a,arr[0]-1);
        }
    }
    public static int[] seachersort(int[] arr,int a,int b){
        int begin=a+1;//扫描指针
        int end=b;//终止指针
        int point=a+1;//等于区间指针
        int pivot=arr[a];//中元值
        while(begin<=end){
            if(pivot<arr[begin]){
                int t=arr[begin];
                arr[begin]=arr[end];
                arr[end]=t;
                end--;
            }else if(pivot==arr[begin]){
                begin++;
            }else {
                int t1=arr[begin];
                arr[begin]=arr[point];
                arr[point]=t1;
                begin++;
                point++;
            }
        }
        point--;
        int t2=arr[point];
        arr[point]=arr[a];
        arr[a]=t2;
        int[] arr2={point,end};
        return arr2;
    }
    public static void main(String args[]) {
        int[] arr = {3, 4, 5, 3, 3, 3, 3, 4, 4, 1, 2, 3, 3, 3};
        System.out.println(sort3(arr,0,arr.length-1));
    }
}
